It is well known to those of ordinary skill in the art that automated systems for use in telecommunications applications typically require the capability of analyzing and identifying signals which are transmitted over a telephone network, such as, for example, the public telephone network, in order to function properly. For example, it is well known that, under certain conditions, specific machine-generated single-frequency signals, denoted as "call-progress" signals, are transmitted over a telephone network to indicate call status conditions. Examples of commonly occurring call status conditions are busy, call-pickup, operator-intercept and so forth and examples of commonly occurring "call-progress" signals which are used to indicate these call status conditions include, without limitation, SIT tones (system intercept tones), answering machine tones, and so forth.
In addition to machine-generated single-frequency signals, it is also well known that automated systems for use in telecommunications voice processing applications require the capability of analyzing and identifying machine-generated communication signals such as ringback, dial tone, dual tone multifrequency (DTMF) tones, and so forth, as well as signals which are produced by human speech, noise and hum, and so forth. Such a capability of analyzing and identifying signals has many uses which are well known to those of ordinary skill in the art. For example, if an automated system places a call over the public telephone network to a predetermined telephone number, the automated system needs to have the capability of analyzing and identifying a whole host of signals which correspond, for example, to ringback, operator interception, human voice response to the telephone call, and so forth. In addition, because certain voice processing applications require a human to respond to queries with specific spoken responses, an automated system in such an application needs to have the capability of analyzing the signal produced by the human speech and of identifying the particular spoken response the called party gave.
In addition to the above-described need for an automated system to have the capability of analyzing and identifying signals, it is well known to those of ordinary skill in the art that it is desirable for the automated system to have the capability of analyzing and identifying signals rapidly enough so that the automated system can take an action which is an appropriate response to the identified signal.
In addition to the above-described need for an automated system to have the capability of analyzing and identifying signals rapidly enough for the automated system to provide an appropriate response to the identified signal, it is well known to those of ordinary skill in the art that the automated system advantageously should have the capability of analyzing and identifying signals which occur in analog signals or in digital signals. Further, in this regard, it is well known that the capability of analyzing and identifying signals which occur in an analog signal typically comprises a step of providing a digital representation of the analog signal and that there are many methods for performing such an analog-to-digital signal conversion. For example, one may use a linear analog-to-digital conversion method or a differential analog-to-digital conversion method--many such differential analog-to-digital conversion methods are well known to those of ordinary skill in the art collectively as delta modulation and there are many different forms thereof, such as, for example, DM (delta modulation), ADPCM (adaptive differential pulse code modulation), CVSD (continuously variable slope delta modulation), and so forth.
It well known to those of ordinary skill in the art that the capability of analyzing and identifying signals referred to above typically requires an automated system to perform an analysis of the frequency spectrum of a signal. In particular, one method which is well known to those of ordinary skill in the art for determining the frequency spectrum of a signal is the discrete Fourier Transform (DFT) which is used to determine the frequency spectrum of a signal. The DFT for a real signal is defined as follows: ##EQU1## where: x.sub.k are a set of N consecutive digital samples of the amplitude of the signal to be analyzed;
n is a frequency index; PA1 R.sub.n and I.sub.n are the real and imaginary frequency coefficients, respectively; and PA1 the frequency bandwidth of each frequency bin n is equal to (Sample Rate)/N. PA1 k=0, . . . , (N-1); n=0, . . . , (N-1); and x.sub.k ranging over all the values of the set of M predetermined digital levels of a sample of the analog signal PA1 N is a predetermined number of samples of the analog signal, which predetermined number of samples are used in analyzing the frequency spectrum; PA1 n is an index of frequency bins of the frequency spectrum; and PA1 x.sub.k, the digital level of a sample, is restricted to being selected from a predetermined set of M possible amplitude values
As one can readily appreciate from the above, an automated system that uses the DFT set forth in eqn. (1) needs to execute multiplications and additions in apparatus such as a processor. Further, in order for the automated system to analyze and identify the signal in order to provide an appropriate response thereto, it needs to execute the DFT rapidly to provide appropriate portions of the frequency spectrum. As a result, the apparatus in the automated system which executes the required multiplications and additions must execute them rapidly. However, as is well known to those of ordinary skill in the art, the need for apparatus which executes multiplications and additions rapidly has been a problem and, as a result, much activity has been directed towards developing methods for providing the frequency spectrum of a signal which reduce the number of multiplications and additions required in order to improve the speed at which such a frequency spectrum can be provided.
One method which is well known to those of ordinary skill in the art for carrying out the DFT set forth in eqn. (1) entails storing the values of the trigonometric functions in a memory. However, this method is inadequate in certain applications because it requires a large number of multiplications and additions to provide the full frequency spectrum of a signal, which number is given by: EQU 2N.sup.2 multiplications+2N.sup.2 additions: all frequency bins
Further improvements in speed occur in certain applications where it is not necessary to compute the coefficients R.sub.n and I.sub.n for each frequency bin in the frequency spectrum. In such a case, one requires the following number of multiplications and additions to provide the coefficients for a single frequency bin: EQU 2N multiplications+2N additions: per bin
Another method which is well known in the art for carrying out the DFT set forth in eqn. (1) is known as the fast Fourier transform (FFT). The FFT is a method which takes advantage of specific symmetry features of trigonometric functions to provide the full frequency spectrum of a signal. The number of multiplications and additions which are required to provide the full frequency spectrum of a signal using the FFT is given by: EQU Nlog.sub.2 N multiplications+Nlog.sub.2 N additions: all frequency bins
Although the FFT requires fewer arithmetic operations to provide the entire frequency spectrum than the DFT, when using the FFT one must necessarily determine the content of all frequency bins in the frequency spectrum. As a result of this, in certain application where it is not necessary to compute the coefficients R.sub.n and I.sub.n for each frequency bin in the frequency spectrum, it can take less time to determine the coefficients for the limited number of frequency bins which are of particular interest with the DFT than it does to determine the coefficients for each frequency bin with the FFT. In addition, a further advantage in using the DFT instead of the FFT in such cases is that the DFT permits one to save a little time by performing the multiplications and additions on the "fly," i.e., as the samples are obtained instead of having to wait untill all N samples have been collected as is required with the FFT.
An additional problem occurs when either the DFT or the FFT is used to provide an analysis of the frequency spectrum of a signal. This problem is that a multiplication in a typical processor takes substantially longer to perform than an addition. For example, when one uses the well known 80188 microprocessor which is available from INTEL Corp., a multiplication can take from 5 to 10 times longer than an addition. As a result of this relatively slow multiplication, use of either the DFT or the FFT is prohibitively inefficient and may prevent an automated telephone interactive system from using such microprocessors for analyzing and identifying signals.
As one can readily appreciate from the above, there is a need in the art for method and apparatus for performing frequency analysis of signals rapidly. Further, there is such a need for method and apparatus for performing such frequency analysis using microprocessors wherein a multiplication takes substantially longer to perform than an addition. Still further, there is a need in the art for method and apparatus for performing such frequency analysis of analog signals and of digital signals, whether the digital signals are digitally encoded by a differential encoding scheme or a non-differential encoding scheme such as a linear encoding scheme, a u-law encoding scheme, an A-law encoding scheme, a pulse code modulation (PCM) encoding scheme and so forth.
Lastly, there is a need in the art for method and apparatus for use in automated systems in telecommunications voice processing applications which can identify and differentiate between certain human responses such as, for example between a human response of "yes" and a human response of "no."